Doubly Linked List

Doubly Linked List 結構

題目：707. Design Linked List

連結：https://leetcode.com/problems/design-linked-list/description/

• 等級：Medium

解題思路

1. 建立double ListNode架構
2. 建立頭尾架構，依需求撰寫新增、刪除。

class ListNode {
    int val;
    ListNode prev;
    ListNode next;
    public ListNode(int val) {
        this.val = val;
        this.prev = null;
        this.next = null;
    }
}

class MyLinkedList {
    ListNode left;
    ListNode right;

    public MyLinkedList() {
        left = new ListNode(-1);
        right = new ListNode(-1);
        left.next = right;
        right.prev = left;
    }
    
    public int get(int index) {
        ListNode curr = left.next;
        while(curr != null && index > 0) {
            curr = curr.next;
            index -= 1;
        }
        if(curr != null && curr != right && index == 0) {
            return curr.val;
        }
        return -1;
    }
    
    public void addAtHead(int val) {
        ListNode node = new ListNode(val);
        ListNode next = left.next;
        ListNode prev = left;
        prev.next = node;
        next.prev = node;
        node.next = next;
        node.prev = prev;
    }
    
    public void addAtTail(int val) {
        ListNode node = new ListNode(val);
        ListNode next = right;
        ListNode prev = right.prev;
        prev.next = node;
        next.prev = node;
        node.next = next;
        node.prev = prev; 
    }
    
    public void addAtIndex(int index, int val) {
        ListNode cur = left.next;
        while (cur != null && index > 0)
        {
            cur = cur.next;
            index--;
        }
        if (cur != null && index == 0)
        {
            ListNode node = new ListNode(val);
            ListNode next = cur;
            ListNode prev = cur.prev;
            prev.next = node;
            node.prev = prev;
            node.next = next;
            next.prev = node;
        }  
    }
    
    public void deleteAtIndex(int index) {
        ListNode cur = left.next;
        while (cur != null && index > 0)
        {
            cur = cur.next;
            index--;
        }
        if (cur != null && cur != right && index == 0)
        {
            ListNode next = cur.next;
            ListNode prev = cur.prev;
            prev.next = next;
            next.prev = prev;
        } 
    }
}

Operation Big-O Time Complexity
Access O(n)
Search O(n)
Insertion O(1)*
Deletion O(1)*